import random


def insertSort():
    for index in range(len(array)):
        itemToBeInserted = array[index]
        sortedPointer = index-1  #代表已排序的最后一个
        while array[sortedPointer]>itemToBeInserted and sortedPointer>-1:
            array[sortedPointer+1] = array[sortedPointer]
            sortedPointer-=1
        array[sortedPointer+1] = itemToBeInserted
    return array

def insertSort2():
    for index in range(1,len(array)):
        itemToBeInserted = array[index]
        sortedPointer = index-1  #代表已排序的最后一个
        while array[sortedPointer]>itemToBeInserted and sortedPointer>0:
            array[sortedPointer+1] = array[sortedPointer]
            sortedPointer-=1
        array[sortedPointer+1] = itemToBeInserted
    return array

def insertSort3(arr):
    if arr and len(arr)<2:
        return arr
    else:
        for i in range(len(arr)):
            j = i-1
            while j>=0 and arr[j]>arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
                j-=1
        return arr


if __name__ == '__main__':
    array = [4,7,7,8,5,10,2,3]
    # print(insertSort())
    # print(insertSort2())
    # print(insertSort3(array))




# FOR Pointer <- 1 TO NumberOfitems - 1
#   ItemToBeinserted <- List [Pointer]
#   Currentitem <- Pointer - 1 // pointer to last item in sorted part of list
#   WHILE (List[Currentitem] > ItemToBeinserted) AND (Currentitem > -1) DO
#       List[Currentitem + l] <- List[Currentitem] // move current item down
#       Currentitem <- Currentitem - 1 // look at the item above
#   ENDWHILE
#   List[Currentitem + 1] <- ItemToBeinserted // insert item
# NEXT Pointer
